//给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。 
//
// 叶子节点 是指没有子节点的节点。 
// 
//
// 示例 1： 
//
// 
//输入：root = [1,2,3,null,5]
//输出：["1->2->5","1->3"]
// 
//
// 示例 2： 
//
// 
//输入：root = [1]
//输出：["1"]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [1, 100] 内 
// -100 <= Node.val <= 100 
// 
// Related Topics 树 深度优先搜索 字符串 二叉树 
// 👍 611 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node4 = new TreeNode(5);
        root.left = node1;
        root.right = node2;
        node1.right = node4;
        new BinaryTreePaths().new Solution().binaryTreePaths(root);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

    /**
     * 这道题目是遍历到所有叶子节点的路径
     * 使用dfs完成的，使用了一个temp集合来存储访问的节点
     * 如果当前节点是叶子节点的话就遍历temp进行添加即可
     * 从两边dfs返回之后需要清除temp最后一个元素才行
     *
     * 二刷和一刷实现方式基本一样
     */
    class Solution {
        List<String> res;
        List<String> temp;
        public List<String> binaryTreePaths(TreeNode root) {
            res = new ArrayList<>();
            temp = new ArrayList<>();
            if (root==null) return res;
            dfs2(root, new StringBuilder());
            return res;
        }
        public void dfs(TreeNode root){
            temp.add(String.valueOf(root.val));
            if (root.left == null && root.right==null){
                StringBuilder s = new StringBuilder(temp.get(0));
                for (int i = 1; i <temp.size() ; i++)
                    s.append("->").append(temp.get(i));
                res.add(s.toString());
            }
            if (root.left!=null)dfs(root.left);
            if (root.right!=null)dfs(root.right);
            temp.remove(temp.size()-1);// TODO 一定要清除最后一个元素
        }

        /**
         * 直接传路径的方法
         */
        public void dfs2(TreeNode root, StringBuilder path){
            if (root.left == null && root.right == null){
                res.add(path.toString()+root.val);
            }else {
                path.append(root.val);
                if (root.left != null) {
                    dfs2(root.left, path.append("->"));
                    path.delete(path.length()-2, path.length());//修复状态
                }
                if (root.right != null) {
                    dfs2(root.right, path.append("->"));
                    path.delete(path.length()-2, path.length());//修复状态
                }
                //删除添加的元素
                path.delete(path.length() - String.valueOf(root.val).length(), path.length());
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)
public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
}






































